package com.leetcode.动态规划;

import java.util.List;

import javax.sound.midi.Soundbank;


/**
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * @author LZF
 *
 */
public class L72编辑距离 {
	
	public static void main(String[] args) {
		int result = minDistance("intention", "execution");
		System.out.println(result);
	}
	/**
	 * dp[i][j]：w1[0,i]转换成w2[0,j]所使用的最小操作数。w1[0,i]表示word1下标0到i的字串
	 * dp[i][j]由以下几种情况得来：
	 * 递推：if(w1[i] == w2[j]) 则dp[i][j]不需要操作，dp[i][j] = dp[i-1][j-1]
	 * else 则需要进行三种操作：插入、删除、替换
	 * 插入:w1插入一个字符，相当于w2删除一个字符，如：w1="ac" w2="abc",w1插入一个'b'，相当于w2删除一个'b'
	 * 因此，插入列入删除一起讨论，以下dp[i][j]套入定义，就好解释多了。
	 * 删除：1、删除w1[i]这个字符，那么就是dp[i][j]=dp[i-1][j] + 1
	 * 2、删除w2[j]这个字符，那么就是dp[i][j]=dp[i][j-1] + 1
	 * 3、删除两个字符，那么就是dp[i][j]=dp[i-1][j-1]+2（这个肯定比替换多出一个操作，因此就舍去）
	 * 替换:不管是替换w1[i]还是w2[j]，都是使得w1[i] == w2[j]，且占一个操作数，因此dp[i][j]=dp[i-1][j-1] + 1
	 * 
	 * dp[i][j]取以上的最小值。
	 * 初始化：
	 * dp[0][0]=(w1[0]==w2[0]) ? 0 : 1 （1就是删除一个字符，最少是一个操作数）
	 * i>1:dp[i][0]=(w1[i]==w2[0]) ? i : min((i+1),dp[i-1][0]+1)
	 * 解释：
	 * i：如果w1[i]==w2[0]，则他们最多只有这一个元素相等（因此w2就是w2[0]这个元素），w1的其他元素都得删去，其他元素有i个
	 * i+1：如果不相等，则删除w1的其他元素i个，再加上替换一个使得w1[i]==w2[0]，因此有i+1个操作数
	 * dp[i-1][0]+1:如果不相等，则删除w1[i]这个字符，占一个操作数，则剩下的操作数就是dp[i-1][0]
	 * 同理，当j>1时，dp[0][j]=(w1[0]==w2[j]) ? j : min((j+1),dp[0][j-1]+1)
	 */
	public static int minDistance(String word1, String word2) {
		int len1 = word1.length();
		int len2 = word2.length();
		 if(len1 == 0 || len2 == 0) return len1 + len2;//如果有一个为0，返回另外一个的长度，相当于另外一个都删除，使得两个空串相等
		 //如果两个为0，则返回0，因此两个都是空串，是相等的。
		int[][] dp = new int[len1][len2];
		dp[0][0] = word1.charAt(0) == word2.charAt(0) ? 0 : 1;
		for(int i = 1;i < len1;i++)
			dp[i][0]=(word1.charAt(i) == word2.charAt(0)) ? i : Math.min((i + 1),dp[i - 1][0]+1);
		for(int j = 1;j < len2;j++)
			dp[0][j]=(word1.charAt(0) == word2.charAt(j)) ? j : Math.min((j + 1),dp[0][j - 1]+1);
		for(int i = 1;i < len1;i++) {
			for(int j = 1;j < len2;j++) {
				if(word1.charAt(i) == word2.charAt(j)) {
					dp[i][j] = dp[i - 1][j - 1];
				}else {
					dp[i][j] = Math.min(dp[i - 1][j - 1] + 1,Math.min(dp[i - 1][j] + 1,dp[i][j - 1] + 1));
				}
			}
		}
		return dp[len1 - 1][len2 - 1];
    }
}
